《算法竞赛入门经典》 第1章 程序设计入门

发表于 | 分类于

第一张讲了些很基本的C/C++常识。

书中一些小的例子。

1
2
3
4
5
6
7
8
9
10
printf("%.1f\n", 8/5);
printf("%d\n", 8.0/5.0);
printf("%.2f\n", 8.0/5);
printf("%.2f\n", 8/5);
0.0
-1717986918
1.60

printf("%.8f\n", 1 + 2 * sqrt(3) / (5 - 0.1));
1.70695951

提示：(5 - 0.1）的过程是，5先变成了浮点数，然后浮点数 + 浮点数。 

1
2
3
4
5
6
7
8
// 1.1圆柱体的表面积
    const double pi = acos(-1.0);
    double r, h, s1, s2, s;
    scanf("%lf%lf", &r, &h);
    s1 = pi * r * r;
    s2 = 2.0 * pi * r;
    s = s1 * 2.0 + s2;
    printf("Ares = %.3f\n", s);
1
2
3
4
5
6
7
8
9
10
// 1.2 三位数反转
    int n;
    scanf("%3d", &n);
    printf("%d%d%d\n", n % 10, n / 10 % 10, n / 100);

    1234
    321

    250
    052
1
2
3
4
5
6
7
8
9
10
11
// 1.2 三位数反转 2
    int n, m;
    scanf("%3d", &n);
    m = (n % 10) * 100 + (n / 10 % 10) * 10 + n / 100;
    printf("%03d\n", m);

    1234
    321

    250
    052
1
2
3
4
5
6
7
8
9
10
// 1.3 变量交换 
    int a, b, temp;
    scanf("%d%d", &a, &b);
    temp = a;
    a = b;
    b = temp;
    printf("%d %d\n", a, b);

    123 456
    456 123
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 1.3 变量交换 2
    int a, b;
    scanf("%d%d", &a, &b);
    a = a + b;
    b = a - b;
    a = a - b;
    printf("%d %d\n", a, b);

//这么理解就很容易：
    a = o, b = x;
    a = o + x；
    b = (o + x) - x; 
      = o
    a = (o + x) - o;
      = x
//完成交换。
1
2
3
4
// 1.3 变量交换 3
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d %d\n", b, a);

大部分时候，我们并不关心实现过程是怎样的，是为了解决问题。
多数竞赛采用黑盒测试，考察的是解决问题的能力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 1.4 鸡兔同笼
    int a, b, m, n;
    scanf("%d%d", &n, &m);
    a = (4 * n - m) / 2;
    b = n - a;
    if(m % 2 == 1 || a < 0 || b < 0) {
        printf("No answer.\n");
    } else{
        printf("%d %d\n", a, b);
    }  

14 32
12 2

10 16
No answer.
1
2
3
4
5
6
7
8
9
10
11
12
// 1.5 三整数排序 (错误)
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(a < b && b < c) printf("%d %d %d\n", a, b, c);
    if(a < c && c < b) printf("%d %d %d\n", a, c, b);
    if(b < a && a < c) printf("%d %d %d\n", b, a, c);
    if(b < c && c < a) printf("%d %d %d\n", b, c, a);
    if(c < b && b < a) printf("%d %d %d\n", c, b, a);
    if(c < a && a < b) printf("%d %d %d\n", c, a, b);

18 06 19
6 18 19
1
2
3
4
5
6
7
8
9
10
11
// 1.5 三整数排序 2
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(a <= b && b <= c) printf("%d %d %d\n", a, b, c);
    else if(a <= c && c <= b) printf("%d %d %d\n", a, c, b);
    else if(b <= a && a <= c) printf("%d %d %d\n", b, a, c);
    else if(b <= c && c <= a) printf("%d %d %d\n", b, c, a);
    else if(c <= b && b <= a) printf("%d %d %d\n", c, b, a);
    else if(c <= a && a <= b) printf("%d %d %d\n", c, a, b);
//最后一句可以改为
    else printf("%d %d %d\n", c, a, b);

错误的方案里面有2个问题：
1.当变量相等的情况出现，方案一就会出问题。如果要考虑相等的情况。
2.加=号是不够的，如果输入1 1 1，会输出6个1 1 1，因此需要用else if。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 1.5 三整数排序 3
    int a, b, c, temp;
    scanf("%d%d%d", &a, &b, &c);
    if(a > b) { temp = a; a = b; b = temp; } //之后a <= b
    if(a > c) { temp = a; a = c; c = temp; } //之后a <= c 且 a <= b依旧成立 
    if(b > c) { temp = b; b = c; c = temp; } //上面一步，最小的确定，然后确定b，c关系
    printf("%d %d %d\n", a, b, c);

15 13 11
11 13 15
//例：
a 15-13-11 11
b 13-15 15-13 
c 11 11-13-15

1.5.2的实验：

1
2
3
4
5
6
7
8
9
10
11
    printf("%d\n", 11111 * 11111);
    printf("%d\n", 111111 * 111111);
    printf("%f\n", 11111.0 * 11111.0);
    printf("%f\n", 1.0 / 0.0);
    printf("%f\n", 0.0 / 0.0);

123454321
-539247567
123454321.000000
1.#INF00
-1.#IND00

1
2
3
4
5
6
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d %d", a, b);

abc 123
2130567168 2686756